package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}
	list := []int{}
	ans := [][]int{}
	currQueue := []*TreeNode{}
	nextQueue := []*TreeNode{}
	currQueue = append(currQueue, root)
	index := 0
	for index < len(currQueue) {
		//加入值
		list = append(list, currQueue[index].Val)
		//将左节点加入下层队列
		if currQueue[index].Left != nil {
			nextQueue = append(nextQueue, currQueue[index].Left)
		}
		//将右节点加入下层队列
		if currQueue[index].Right != nil {
			nextQueue = append(nextQueue, currQueue[index].Right)
		}
		if index == len(currQueue)-1 {
			ans = append(ans, list)
			list = []int{}
			currQueue, nextQueue = nextQueue, []*TreeNode{}
			index = 0
			continue
		}
		index++
	}
	return ans
}

func main() {
	node5 := &TreeNode{Val: 7}
	node4 := &TreeNode{Val: 15}
	node3 := &TreeNode{Val: 20, Left: node4, Right: node5}
	node2 := &TreeNode{Val: 9}
	node1 := &TreeNode{Val: 3, Left: node2, Right: node3}
	order := levelOrder(node1)
	for i := 0; i < len(order); i++ {
		for j := 0; j < len(order[i]); j++ {
			print(order[i][j])
		}
		println()
	}

}
